package com.hardy.leetcode;

/**
 * User: Ruijie Date: 2016/9/20
 */
public class WordSearch {

    public static int[][] direction = {{0, 1}, {0, -1}, {-1, 0}, {1, 0}};
    public static int[][] flag;

    public static boolean exist(char[][] board, String word) {
        flag = new int[board.length][board[0].length];
        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[0].length; j++) {
                if(board[i][j]==word.charAt(0)){
                    int row = i;
                    int col = j;
                    flag[row][col]=1;
                    if (dfs(row, col, board, 0, word)) {
                        return true;
                    }
                    flag[row][col]=0;
                }
            }
        }
        return false;
    }

    private static boolean dfs(int row, int col, char[][] board, int index, String word) {
        if (index == word.length()-1) {
            return true;
        }
        for (int i = 0; i < direction.length; i++) {
            int nrow = row + direction[i][0];
            int ncol = col + direction[i][1];
            if (nrow == -1 || nrow == board.length || ncol == -1 || ncol == board[0].length
                || flag[nrow][ncol] == 1 || word.charAt(index+1) != board[nrow][ncol]) {
                continue;
            } else {
                flag[nrow][ncol] = 1;
                if (dfs(nrow, ncol, board, index + 1, word)) {
                    return true;
                }
                flag[nrow][ncol] = 0;
            }

        }
        return false;
    }

    public static void main(String[] args) {
        char[][] chs = {{'A', 'B', 'C', 'E'}, {'S', 'F', 'C', 'S'}, {'A', 'D', 'E', 'E'}};
        char[][] chs1 = {{'a'}};
        System.out.println(exist(chs, "ABCCED"));
        System.out.println(exist(chs, "SEE"));
        System.out.println(exist(chs, "ABCB"));
        System.out.println(exist(chs1, "b"));
    }
}
